#
# @lc app=leetcode.cn id=74 lang=python3
#
# [74] 搜索二维矩阵
#

# @lc code=start

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        rowCount = len(matrix)
        columnCount = len(matrix[0])
        
        left = 0
        right = rowCount * columnCount - 1
        while left <= right:
            mid = (left + right) // 2
            
            row = mid // columnCount
            column =  mid % columnCount
            if matrix[row][column] == target:
                return True
            elif matrix[row][column] < target:
                left = mid + 1
            elif matrix[row][column] > target:
                right = mid - 1
           
            
        return False
    
Solution().searchMatrix([[1,3]], 3)
# @lc code=end

